/**
题目:
    给定一个二叉树，返回它的中序 遍历。
    示例:
    输入: [1,null,2,3]
       1
        \
        2
        /
        3
    输出: [1,3,2]
    进阶: 递归算法很简单，你可以通过迭代算法完成吗？
思路:
    如果当前节点不为nil或者栈不为空就进入循环
    如果当前节点不为空就将其加入栈中并遍历其左子树
    左子树遍历完毕后从栈中拿到栈顶节点 打印并遍历其右子树
效果:
    执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
    内存消耗：2 MB, 在所有 Go 提交中击败了75.59%的用户
*/
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    s := make([]*TreeNode,0)
    cur, res := root, make([]int, 0)
    for cur != nil || len(s) > 0{
        for cur != nil{
            s = append(s, cur)
            cur = cur.Left
        }
        cur = s[len(s)-1]
        s = s[:len(s)-1]
        res = append(res, cur.Val)
        cur = cur.Right
    }
    return res
}